package ViolenceRecursive;

/**
 * 给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值 desired。返回express能有多少种组合方式，可以达到desired的结果。
 * 【举例】
 * express="1^0|0|1"，desired=false
 * 只有1^((o|0)|1)和1^(O|(0|1))的组合可以得到false， ->  返回2。
 * express="1"，desired=false  -> 无组合则可以得到false，返回0
 *
 * @author Liaorun
 */
public class ExpressionNumber {

    public static void main(String[] args) {
        // 暴力递归
        System.out.println(num1("1^0|0|1", false));
        // 动态规划表
        System.out.println(dpLive("1^0|0|1", false));
    }

    /**
     * 检查是否有不合题意的字符出现
     *
     * @param exp
     * @return
     */
    public static boolean isValid(char[] exp) {
        if ((exp.length & 1) == 0) {
            // 表达式长度为偶数不合规
            return false;
        }

        // 偶数位置必须为1 or 0
        for (int i = 0; i < exp.length; i += 2) {
            if (exp[i] != '1' && (exp[i] != '0')) {
                return false;
            }
        }
        // 奇数位置必须为 & or ^ or |
        for (int i = 1; i < exp.length; i += 2) {
            if (exp[i] != '&' && exp[i] != '|' && exp[i] != '^') {
                return false;
            }
        }

        return true;
    }

    public static int num1(String express, boolean desired) {
        if (express == null || "".equals(express)) {
            return 0;
        }

        char[] exp = express.toCharArray();
        if (!isValid(exp)) {
            return 0;
        }

        return p(exp, desired, 0, exp.length - 1);
    }

    /**
     * @param exp     表达式
     * @param desired 期望表达式经过括号划分后返回的值
     * @param l
     * @param r
     * @return
     */
    private static int p(char[] exp, boolean desired, int l, int r) {
        // base case
        if (l == r) {
            if (exp[l] == '1') {
                // 当前值为1
                // return 目标 == true ? 能返回1 : 不可能返回0
                return desired ? 1 : 0;
            } else {
                // 当前值为0
                // return 目标 == true ? 能返回0 : 不可能返回1
                return desired ? 0 : 1;
            }
        }
        // 统计划分组合的方式的变量
        int res = 0;
        if (desired) {
            // 期待为desired == true
            for (int i = l + 1; i < r; i += 2) {
                switch (exp[i]) {
                    case '&':
                        // 期待左右都为true的组合方法数
                        res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
                        break;
                    case '|':
                        // 左右有一个true即可
                        res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
                        res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
                        res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
                        break;
                    case '^':
                        // 左右两侧不同为1
                        res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
                        res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
                        break;
                    default:
                        throw new IllegalStateException("Unexpected value: " + exp[i]);
                }
            }
        } else {
            for (int i = l + 1; i < r; i += 2) {
                switch (exp[i]) {
                    case '&':
                        // 左右有一个false即可
                        res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
                        res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
                        res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
                        break;
                    case '|':
                        // 期待左右都为false的组合方法数
                        res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
                        break;
                    case '^':
                        // 左右两侧相同为0
                        res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
                        res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
                        break;
                    default:
                        throw new IllegalStateException("Unexpected value: " + exp[i]);
                }
            }
        }
        return res;
    }


    public static int dpLive(String express, boolean desired) {
        char[] str = express.toCharArray();
        int n = str.length;

        int[][] trueMap = new int[n][n];
        int[][] falseMap = new int[n][n];

        // 根据base case 把对角线填好
        // i 每次 + 2,是要跳过偶数位置的符号
        for (int i = 0; i < n; i += 2) {
            trueMap[i][i] = str[i] == '1' ? 1 : 0;
            falseMap[i][i] = str[i] == '0' ? 1 : 0;
        }

        for (int row = n - 3; row >= 0; row -= 2) {
            // col = row + 2开始，是因为， col = row 的base 已经赋值了
            for (int col = row + 2; col < n; col += 2) {
                // row..col trueMap falseMap
                for (int i = row + 1; i < col; i += 2) {
                    switch (str[i]) {
                        case '&':
                            trueMap[row][col] += trueMap[row][i - 1] * trueMap[i + 1][col];
                            break;
                        case '|':
                            trueMap[row][col] += trueMap[row][i - 1] * falseMap[i + 1][col];
                            trueMap[row][col] += falseMap[row][i - 1] * trueMap[i + 1][col];
                            trueMap[row][col] += trueMap[row][i - 1] * trueMap[i + 1][col];
                            break;
                        case '^':
                            trueMap[row][col] += trueMap[row][i - 1] * falseMap[i + 1][col];
                            trueMap[row][col] += falseMap[row][i - 1] * trueMap[i + 1][col];
                            break;
                        default:
                            throw new IllegalStateException("Unexpected value: " + str[i]);
                    }

                    switch (str[i]) {
                        case '&':
                            falseMap[row][col] += trueMap[row][i - 1] * falseMap[i + 1][col];
                            falseMap[row][col] += falseMap[row][i - 1] * trueMap[i + 1][col];
                            falseMap[row][col] += falseMap[row][i - 1] * falseMap[i + 1][col];
                            break;
                        case '|':
                            falseMap[row][col] += falseMap[row][i - 1] * falseMap[i + 1][col];
                            break;
                        case '^':
                            falseMap[row][col] += trueMap[row][i - 1] * trueMap[i + 1][col];
                            falseMap[row][col] += falseMap[row][i - 1] * falseMap[i + 1][col];
                            break;
                        default:
                            throw new IllegalStateException("Unexpected value: " + str[i]);
                    }
                }
            }
        }
        return desired ? trueMap[0][n - 1] : falseMap[0][n - 1];
    }
}
